#include <list>
#include <iostream>

using namespace std;

bool isWord(const char *chStr, int length, list<char*> dict);

char* splitWords(const char *str, list<char*> &dict){
	list<int> lengthList;
	int index = 0;
	int len = 1;
	int length = strlen(str);
	do{
		while(len <= length - index){			
			if(isWord(str + index, len, dict)){
				lengthList.push_back(len);
					index += len;
					len = 1;
			}
			else{
				++len;
			}
		}
		// Complete splitting
		if(index > length - 1)
			break;
		// backtracking
		len = lengthList.back();
		lengthList.pop_back();
		index -= len;
		++len;
	}while(!lengthList.empty());

	// Not a valid string
	if(lengthList.empty())
		return NULL;

	// Insert blankspace
	len = length + lengthList.size() + 1;
	char *result = new char[len];
	memset(result, '\0', len);
	index = 0;
	int index2 = 0;
	for(list<int>::iterator it = lengthList.begin(); it != lengthList.end(); ++it){
		for(int i = 0; i < *it; i ++){
			result[index++] = str[index2++];
		}
		result[index++] = ' ';
	}

	return result;
}

bool isWord(const char *chStr, int length, list<char*> dict){
	if(0 == length)
		return true;

	for(list<char*>::iterator it = dict.begin(); it != dict.end(); ++it){
		if(0 == strlen(*it) || strlen(*it) != length)
			continue;
		int i = 0;
		for(; i  < length; ++i){
			if(chStr[i] != (*it)[i] && chStr[i] != (*it)[i] - 32){
				break;
			}
		}
		if(i == length)
			return true;
	}	

	return false;
}

int smain(){	
	char* str = "Longlongagotherewasatigerintheforest";
	list<char*> dict;
	dict.push_back("a");	
	dict.push_back("ago");
	// dict.push_back("go");
	dict.push_back("got");
	dict.push_back("fore");
	dict.push_back("forest");
	dict.push_back("he");
	dict.push_back("in");
	dict.push_back("long");
	dict.push_back("other");
	dict.push_back("rest");
	dict.push_back("sat");
	dict.push_back("the");
	dict.push_back("there");
	dict.push_back("tiger");
	dict.push_back("was");

	char *result = splitWords(str, dict);
	
	cout << (NULL == result? "Not a valid string" : result)<< endl;

	return 0;
}